package com.test;

import java.util.Arrays;

/**
 * 归并排序
 *
 * 时间复杂度为o(nlogn) 空间复杂度为 o(n) + o(logn)
 *
 * 说明:
 * 把两个(或者两个以上)的有序表合并成一个新的有序表 , 把待排序序列分为若干个序列 , 每个子序列都是有序的
 * 然后再把有序的子序列合并为整体有序序列
 *
 * Created by abing on 2015/11/26.
 */
public class SuanFaMerge {

    public static void main(String[] args){
        int[] data = {1,2,3,5,21,43,65,87,22,33,44,55,99};
        sort(data , 0 , data.length-1);
    }

    public static void sort(int[] data , int left , int right){
        if (left < right){
            int center = (right + left)/2;
            System.out.println("11 : "+left + " " + center + " " + right);
            sort(data, left, center);
            System.out.println("22 : "+left + " " + center + " " + right);
            sort(data, center + 1, right);
            System.out.println("33 : "+left + " " + center + " " + right);
            merge(data , left ,center , right);
        }
    }

    public static void merge(int[] data , int left , int center , int right){
//        System.out.println(left + " " + center + " " + right);
        int[] tmpArr = new int[data.length];
        int mid = center+1;
        //记录中间数组的索引
        int third = left;
        int tmp = left;
        while (left <= center && mid <= right){
            //从两个数组中取出最小的放入中间数组
            if (data[left] <= data[mid]){
                tmpArr[third++] = data[left++];
            }else {
                tmpArr[third++] = data[mid++];
            }
        }
        //剩余部分依次放入中间数组
        while (mid <= right){
            tmpArr[third++] = data[mid++];
        }
        while (left <= center){
            tmpArr[third++] = data[left++];
        }
        //将中间数组中的内容复制回原数组
        while (tmp <= right){
            data[tmp] = tmpArr[tmp++];
        }
        System.out.println(Arrays.toString(data));


    }
}
